//
// Created by durandal on 2024/1/18.
//

#ifndef ALGORITHM_SORT_H
#define ALGORITHM_SORT_H
#include <vector>
#include <chrono>
#include <functional>
#include <iostream>

template<typename T>
void execwith_time_measurement(std::function<void()> func) {
    auto startTime = std::chrono::high_resolution_clock::now();
    func();
    auto endTime = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(endTime - startTime);
    std::cout << "execute time: " << duration.count() << " ms" << std::endl;
}

namespace {
    template<typename T>
    typename std::vector<T>::iterator
    find_min(typename std::vector<T>::iterator it1, typename std::vector<T>::iterator it2) {
        auto min = it1;
        for (auto it = it1; it != it2; it++)
            if (*it < *min)
                min = it;

        return min;
    }

    template<typename T>
    void swap(typename std::vector<T>::iterator it1, typename std::vector<T>::iterator it2) {
        if (it1 != it2) {
            auto temp = *it1;
            *it1 = *it2;
            *it2 = temp;
        }
    }

    template<typename T>
    void exchange(std::vector<T> &list, int i1, int i2) {
        if (list[i1] != list[i2]) {
            T temp = list[i1];
            list[i1] = list[i2];
            list[i2] = temp;
        }
    }

    template<typename T>
    void local_merge(std::vector<T> &list, int low, int high, int mid) {
        std::vector<T> temp_list = list;
        int cur_l = low;
        int cur_h = mid + 1;
        for (int index = low; index <= high; index++) {
            if (cur_l > mid) list[index] = temp_list[cur_h++];
            else if (cur_h > high) list[index] = temp_list[cur_l++];
            else if (temp_list[cur_l] < temp_list[cur_h]) list[index] = temp_list[cur_l++];
            else list[index] = temp_list[cur_h++];
        }
    }

    template<typename T>
    void htol_merge_sort_(std::vector<T> &list, int l, int h) {
        if (l >= h) return;
        int mid = (l + h) / 2;
        htol_merge_sort_(list, l, mid);
        htol_merge_sort_(list, mid + 1, h);
        local_merge(list, l, h, mid);
    }

    template<typename T>
    int partition(std::vector<T> &list, int l, int h) {
        T needPartition = list[l];
        // point to
        int ptol = l, ptoh = h + 1;
        while (ptoh > ptol) {
            for (; list[++ptol] < needPartition;) if (ptol == h) break;
            for (; list[--ptoh] > needPartition;) if (ptoh == l) break;
            if (ptol >= ptoh) break;
            exchange(list, ptol, ptoh);
        }
        exchange(list, l, ptoh);
        return ptoh;
    }

    template<typename T>
    void quick_sort_(std::vector<T> &list, int l, int h) {
        if (h <= l) return;
        int part = partition(list, l, h);
        quick_sort_(list, l, part - 1);
        quick_sort_(list, part + 1, h);
    }

    /*
     * slow when same elements are less
     */

    /*
    template<typename T>
    int quick_sort_3_way_(std::vector<T>& list, int l, int h) {
        int i_same = l;
        int ptol = l, ptoh = h + 1;
        T needPartition = list[l];
        for (; i_same <= h; ) {
            for (; list[++i_same] < needPartition; ) if (ptol == h) break;
            for (; list[--ptoh] > needPartition; ) if (ptoh == l) break;
            if (list[i_same] == needPartition) {
                exchange(list, ptol, i_same);
                break;
            }
            if (list[ptoh] == needPartition) {
                exchange(list, i_same, ptoh);
            }
            if (i_same >= ptoh) break;
            exchange(list, i_same, ptoh);
        }
        exchange(list, l, i_same);
        return i_same;
    }
}
     */

    template<typename T>
    void quick_sort_3_way_(std::vector<T> &list, int l, int h) {
        if (h <= l) return;
        T needPartition = list[l];
        int ptol = l, ptoh = h, i_same = l + 1;
        for (; i_same <= ptoh;) {
            if (list[i_same] < needPartition) exchange(list, i_same++, ptol++);
            else if (list[i_same] > needPartition) exchange(list, i_same, ptoh--);
            else i_same++;
        }
        quick_sort_3_way_(list, l, ptol - 1);
        quick_sort_3_way_(list, ptoh+1, h);
    }

}


template<typename T>
void selection_sort(std::vector<T>& list) {
    for (auto it1 = list.begin(); it1 != list.end(); it1++) {
        auto min = find_min<T>(it1, list.end());
        swap<T>(it1, min);
    }
}

/*
 * use std::copy to move when select one element
 * or can use exchange move,
 * but I think std::copy is better as the elements in std::vector is a continuous area
 */
template<typename T>
void insertion_sort(std::vector<T>& list) {
    for (auto it1 = list.begin(); it1 != list.end(); it1++) {
        auto it2 = list.begin();
        for (; *it2 < *it1; it2++);
        if (it2 != it1) {
            auto temp = *it1;
            std::copy(it2, it1, it2+1);
            *it2 = temp;
        }
    }
}

template<typename T>
void shell_sort(std::vector<T>& list, int interval) {
    for (int cur_interval = interval; cur_interval >= 1; cur_interval /= 3)
        for (int index = cur_interval; index < list.size(); index++)
            for (int cur_index = index; cur_index >= cur_interval &&
                                        list[cur_index] < list[cur_index - cur_interval]; cur_index -= cur_interval)
                exchange(list, cur_index, cur_index - cur_interval);
}

template<typename T>
void htol_merge_sort(std::vector<T>& list) {
    htol_merge_sort_(list, 0, list.size() - 1);
}

template<typename T>
void ltoh_merge_sort(std::vector<T>& list) {
    int cur_l = 0;
    int cur_h = list.size() - 1;
    for (int cur_interval = 1; cur_interval < list.size(); cur_interval *= 2)
        for (int cur_i = 0; cur_i + cur_interval < list.size(); cur_i = cur_i + cur_interval * 2)
            local_merge(list, cur_i,
                        cur_i + 2 * cur_interval <= list.size() - 1 ? cur_i + cur_interval * 2 - 1 : list.size() - 1,
                        cur_i + cur_interval - 1);
}

template<typename T>
void quick_sort(std::vector<T>& list) {
    quick_sort_(list, 0, list.size()-1);
}

template<typename T>
void quick_sort_3_way(std::vector<T>& list) {
    quick_sort_3_way_(list, 0, list.size()-1);
}



#endif //ALGORITHM_SORT_H
